package LeetCode.Medium;

/*
把一个长度为n的绳子剪断为m份，使他们的积最大
 */
public class Question005 {
    public int cuttingRope(int n){
//        int a = n / 3;
//        int b = n % 3;
//        if(b==0) return (int) Math.pow(3, a);
//        if(b == 1) return (int) (Math.pow(3, a-1) * 4);
//        return (int) (Math.pow(3,a) * 2);
//        // 大数求余
//        if(n <= 3) return n - 1;
//        int b = n % 3, p = 1000000007;
//        long rem = 1, x = 3;
//        for(int a = n / 3 - 1; a > 0; a /= 2) {
//            if(a % 2 == 1) rem = (rem * x) % p;
//            x = (x * x) % p;
//        }
//        if(b == 0) return (int)(rem * 3 % p);
//        if(b == 1) return (int)(rem * 4 % p);
//        return (int)(rem * 6 % p);



         /*
        dp五部曲:
        1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i]
        2.状态转移:dp[i]有两种途径可以转移得到
            2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个
            2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2
            两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值
        3.初始化:初始化dp[1]=1即可
        4.遍历顺序:显然为正序遍历
        5.返回坐标:返回dp[n]
        */
        // 定义dp数组
//        int[] dp = new int[n + 1];
//        // 初始化
//        dp[1] = 1;  // 指长度为1的单独乘积为1
//        // 遍历[2,n]的每个状态
//        for(int i = 2; i <= n; i++) {
//            for(int j = 1; j <= i - 1; j++) {
//                // 求出两种转移情况(乘积个数为2和2以上)的最大值
//                int tmp = Math.max(dp[j] * (i - j), j * (i - j));
//                dp[i] = Math.max(tmp, dp[i]);
//            }
//        }
//        return dp[n];


        // f(0)=1,f(1)=1,f(2)=1*1,f(3)=2
        if (n <= 3) {
            return Math.max(n - 1, 1);
        }
        // dp思路：砍成两段的最大乘积是 f(n) = f(x)*f(n-x)
        // f(2)虽然=1，在计算的时候的等于2，比如4=2*2=4,不能是1*1
        // f(3)虽然=2，在计算的时候的等于3，比如6=3*3=9,不能是2*2
        // 也就是说在dp计算的时候,f(x)的最小值只能是x,不能小于x
        // 在x>=4的时候计算出来都是大于x,所以不需要特殊定义
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        int ans = 1;
        for (int i = 4; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                ans = Math.max(ans, f[j] * f[i - j]);
            }
            f[i] = ans;
            ans = 0;
        }
        return f[n];
    }
}
